package com.lw.leetcode.dp.b;

import java.util.Arrays;

/**
 * 1833. 雪糕的最大数量
 *
 * @Author liw
 * @Date 2021/7/2 9:29
 * @Version 1.0
 */
public class MaxIceCream {

    public static void main(String[] args) {
        MaxIceCream test = new MaxIceCream();
//        int[] arr = {1,3,2,4,1};
//        int k = 7;
//        int[] arr = {1,6,3,1,2,5};
//        int k = 11;
        int[] arr = {1534, 1390, 890, 1084, 1702, 1354, 1734, 288, 1282, 2, 624, 1902, 106, 1818, 386, 1718, 663, 992, 473, 579, 962, 657, 1604, 1362, 1964, 812, 463, 123, 366, 367, 666, 194, 1298, 1842, 1232, 694, 494, 58, 282, 498, 122, 622, 562, 2, 1383, 1271, 1383, 967, 2, 477, 1270, 42, 1986, 1592, 613, 726, 426, 108, 1086, 314, 1786, 1890, 118, 898, 527, 690, 1487, 46, 202, 1946, 14, 775, 32, 274, 1039, 1362, 815, 1538, 66, 999, 1946, 19, 1546, 87, 1662, 146, 954, 1047, 1452, 1301, 622, 34, 1918, 1952, 1704, 702, 623, 226, 1452, 117, 302, 842, 1826, 1592, 1653, 1802, 87, 1457, 1893, 1276, 535, 1869, 446, 1572, 182, 1714, 788, 74, 328, 1382, 799, 1908, 140, 1969, 262, 1618, 907, 436, 1762, 1796, 211, 74, 386, 1007, 504, 698, 894, 1774, 213, 852, 1606, 171, 390, 1192, 1114, 402, 214, 1020, 1517, 1538, 1112, 737, 1570, 434, 84, 834, 286, 530, 524, 186, 261, 1702, 1218, 1668, 397, 594, 1530, 897, 980, 1100, 1014, 1233, 1550, 1944, 309, 1426, 541, 678, 1815, 1906, 900, 212, 1657, 412, 1277, 1808, 1104, 2, 156, 1872, 1702, 718, 427, 1670, 1875, 800, 124, 1328, 172, 802, 473, 818, 670, 1722, 1835, 1056, 82, 1227, 1554, 1973, 127, 1794, 1942, 767, 1796, 1644, 1896, 1067, 501, 77, 1253, 1410, 1602, 552, 34, 1490, 1336, 1278, 1486, 122, 1322, 1002, 1888, 1442, 1010, 835, 1962, 539, 702, 970, 938, 1952, 837, 242, 471, 436, 1650, 1322, 1362, 797, 1446, 1793, 1730, 1685, 1957, 1834, 936, 657, 1918, 172, 1802, 881, 1759, 1625, 762, 1066, 1748, 1722, 450, 178, 708, 916, 1002, 574, 296, 1277, 1380, 1173, 114, 1663, 286, 210, 548, 758, 931, 1353, 1252, 1466, 82, 742, 322, 1627, 584, 1777, 703, 1017, 470, 1514, 1862, 316, 1375, 512, 1828, 1687, 1264, 562, 1308, 482, 1170, 1908, 1437, 1374, 202, 1404, 1569, 1298, 1238, 735, 1970, 1780, 972, 222, 1156, 1117, 1490, 348, 182, 1782, 1374, 1186, 532, 967, 711, 602, 18, 1583, 1068, 1252, 1474, 762, 1802, 654, 1108, 886, 1732, 1742, 1875, 202, 1011, 656, 1630, 74, 1471, 42, 1666, 214, 966, 1834, 1341, 1986, 1414, 652, 1316, 186, 1729, 1170, 542, 1849, 475, 161, 1296, 1962, 307, 762, 384, 1430, 1652, 1494, 766, 476, 1322, 850, 432, 1497, 374, 98, 920, 1622, 1522, 1798, 1256, 1554, 260, 752, 1548, 1320, 1810, 1502, 1306, 940, 1172, 897, 519, 770, 987, 1106, 1450, 1370, 1250, 1627, 898, 112, 1930, 574, 252, 741, 1841, 1762, 632, 1495, 984, 1807, 1669, 1262, 892, 32, 466, 1647, 722, 1204, 34, 670, 471, 1162, 82, 487, 1840, 168, 1233, 371, 402, 1042, 342, 1034, 1162, 150, 218, 186, 1616, 295, 1000, 1938, 1078, 792, 82, 1308, 588, 902, 1318, 1781, 771, 266, 1602, 1462, 1287, 327, 1142, 638, 905, 663, 706, 859, 1780, 1145, 1048, 754, 354, 1678, 1769, 1374, 1774, 399, 1810, 1944, 642, 90, 1356, 1163, 1322, 960, 1097, 1070, 1458, 1145, 530, 482, 1550, 1022, 1602, 338, 1642, 1628, 242, 24, 1353, 1426, 1838, 1002, 1193, 674, 1412, 1582, 1457, 1909, 922, 524, 1922, 642, 418, 646, 1122, 1682, 194, 6, 866, 1014, 93, 1248, 562, 1667, 1456, 282, 386, 1473, 1752, 1937, 512, 1013, 1202, 552, 1314, 554, 661, 272, 1926, 1394, 1414, 394, 1848, 386, 742, 1340, 310, 1023, 1426, 1792, 447, 114, 50, 832, 906, 1651, 1410, 1112, 1905, 1040, 677, 812, 1939, 1064, 1052, 202, 940, 386, 602, 216, 1240, 434, 1592, 1942, 1301, 1224, 1112, 770, 573, 657, 309, 1692, 1887, 1567, 1473, 1708, 1342, 821, 605, 1602, 1499, 1090, 109, 1764, 610, 1903, 26, 120, 594, 852, 518, 205, 832, 691, 1817, 554, 1245, 897, 1620, 1487, 1907, 626, 1326, 782, 1477, 708, 377, 1154, 718, 1938, 276, 402, 920, 1322, 202, 1617, 1124, 1490, 1232, 164, 207, 1662, 1218, 834, 1377, 1132, 842, 1982, 822, 1260, 82, 1228, 1672, 738, 1575, 1682, 1602, 1954, 1277, 608, 1732, 712, 1281, 102, 442, 346, 519, 1811, 402, 164, 2, 1622, 320, 188, 1626, 1643, 1222, 1922, 387, 258, 930, 150, 1466, 1307, 67, 2, 1702, 1702, 734, 1064, 58, 1502, 994, 1548, 622, 885, 1513, 220, 1225, 1486, 352, 1200, 973, 1522, 1346, 162, 834, 1310, 1917, 876, 1348, 1032, 28, 1466, 210, 228, 1394, 668, 1722, 430, 1803, 796, 800, 302, 336, 770, 586, 1481, 630, 1495, 930, 290, 890, 1558, 114, 452, 1225, 1977, 1327, 91, 1830, 1188, 1226, 1978, 736, 900, 1048, 1864, 1920, 757, 1006, 1475, 1922, 18, 595, 1048, 744, 362, 1018, 1694, 448, 1812, 706, 1362, 1140, 1182, 1938, 1466, 42, 1482, 1186, 360, 281, 558, 1402, 1068, 1384, 493, 607, 1162, 1434, 1602, 276, 652, 1666, 241, 310, 930, 165, 1045, 322, 1496, 1314, 1493, 482, 932, 426, 631, 1932, 2, 852, 2, 402, 457, 1343, 374, 2, 302, 875, 493, 711, 1986, 394, 783, 1558, 1178, 1367, 1310, 669, 1138, 1585, 1376, 242, 803, 1704, 700, 1197, 1650, 1580, 1887, 42, 1602, 1516, 1206, 1954, 898, 841, 1408, 1545, 832, 1583, 1838, 757, 6, 58, 756, 1202, 1096, 583, 797, 911, 1260, 1187, 1696, 995, 200, 1838, 1342, 1593, 727, 488, 749, 390, 1470, 11, 594, 104, 1910, 1650, 1234, 557, 1079, 1167, 1546, 1152, 740, 289, 1618, 594, 254, 162, 1770, 32, 1836, 794, 174, 422, 1382, 1902, 186, 954, 472, 1362, 1362, 1252, 364, 1158, 757, 618, 542, 1820, 1006, 1434, 594, 1722, 962, 1497, 117, 1742, 756, 970, 7, 946, 1544, 1712, 1802, 1502, 1159, 1826, 623, 550, 330, 583, 1273, 768, 45, 1185, 596, 768, 11, 1802, 782, 1164, 1209, 1130, 902, 944, 1143, 1350, 1002, 622, 440, 802, 183, 294, 1292, 366, 292, 1096, 974, 1434, 466, 290, 576, 673, 1594, 1866, 1422, 1804, 1502, 1956, 1642, 12, 53, 1206, 613, 1917, 225, 1021, 246, 748, 603, 602, 1128, 707, 1438, 1267, 74, 579, 602, 632, 674, 1654, 1302, 290, 127, 698, 1368, 1752, 88, 432, 1155, 202, 707, 1176, 1774, 70, 1081, 1894, 91, 902, 1080, 366, 157};
        int k = 845057;

        long l = System.currentTimeMillis();
        int i = test.maxIceCream(arr, k);
        System.out.println(System.currentTimeMillis() - l);
        System.out.println(i);
    }


    /**
     * 抄的，贪心--计数排序 98%
     *
     * @param costs
     * @param coins
     * @return
     */
    public int maxIceCream(int[] costs, int coins) {
        int[] freq = new int[100001];
        for (int cost : costs) {
            freq[cost]++;
        }
        int count = 0;
        for (int i = 1; i <= 100000; i++) {
            if (coins >= i) {
                int curCount = Math.min(freq[i], coins / i);
                count += curCount;
                coins -= i * curCount;
            } else {
                break;
            }
        }
        return count;
    }


    /**
     * 贪心--快速排序9%
     *
     * @param costs
     * @param coins
     * @return
     */
    public int maxIceCream2(int[] costs, int coins) {
        Arrays.sort(costs);
        int item = 0;
        int length = costs.length;
        for (int i = 0; i < length; i++) {
            item += costs[i];
            if (item > coins) {
                return i;
            }
        }
        return length;
    }


    /**
     * 背包--超时
     *
     * @param costs
     * @param coins
     * @return
     */
    public int maxIceCream3(int[] costs, int coins) {
        int[] arr = new int[coins + 1];
        for (int cost : costs) {
            for (int i = coins; i >= cost; i--) {
                arr[i] = Math.max(arr[i], arr[i - cost] + 1);
            }
        }
        return arr[coins];
    }


}
